package com.xyhuo.leetcode.january;

import com.xyhuo.leetcode.common.TreeNode;

import java.util.ArrayList;
import java.util.List;

/**
 * 不同的二叉搜索树Ⅱ
 * https://leetcode.cn/problems/unique-binary-search-trees-ii/
 *
 * @time 2024/1/5
 */
public class GenerateTrees {

//    public static void main(String[] args) {
//        GenerateTrees gt = new GenerateTrees();
//        gt.generateTrees(3);
//    }

    public List<TreeNode> generateTrees(int n) {
        return search(1, n);
    }


    private List<TreeNode> search(int left, int right) {
        if (left > right) {
            return null;
        }
        List<TreeNode> ans = new ArrayList<>();
        if (left == right) {
            ans.add(new TreeNode(left));
            return ans;
        }
        for (int i = left; i <= right; i++) {
            List<TreeNode> leftTree = search(left, i - 1);
            List<TreeNode> rightTree = search(i + 1, right);

            if (null != leftTree && null != rightTree) {
                for (int j = 0; j < leftTree.size(); j++) {
                    for (int k = 0; k < rightTree.size(); k++) {
                        TreeNode root = new TreeNode(i);
                        root.left = copyTree(leftTree.get(j));
                        root.right = copyTree(rightTree.get(k));
                        ans.add(root);
                    }
                }
            } else if (null == leftTree && null != rightTree) {
                for (int j = 0; j < rightTree.size(); j++) {
                    TreeNode root = new TreeNode(i);
                    root.right = copyTree(rightTree.get(j));
                    ans.add(root);
                }
            } else if (null != leftTree && null == rightTree) {
                for (int j = 0; j < leftTree.size(); j++) {
                    TreeNode root = new TreeNode(i);
                    root.left = copyTree(leftTree.get(j));
                    ans.add(root);
                }
            }
        }
        return ans;
    }

    private TreeNode copyTree(TreeNode root) {
        if (null == root) {
            return null;
        }
        TreeNode newNode = new TreeNode(root.val);
        newNode.left = copyTree(root.left);
        newNode.right = copyTree(root.right);
        return newNode;
    }
}
